// 08-图9 关键活动
#include <stdio.h>
#include <stdlib.h>

/* 队列 ************************/
#ifndef QueueElementType
#define QueueElementType int
#endif

typedef struct LinkedNode LinkedNode;
struct LinkedNode {
    QueueElementType data;
    LinkedNode* next;
};

typedef struct Queue Queue;
struct Queue {
    // 队列的头尾节点
    LinkedNode* head;
    LinkedNode* tail;
};

Queue* createQueue() {
    Queue* queue = (Queue*) malloc(sizeof(Queue));
    queue->head = queue->tail = NULL;
    return queue;
}

int isEmptyQueue(Queue *queue) {
    return queue->head == NULL;
}

void enQueue(Queue *queue, QueueElementType data) {
    LinkedNode* node = (LinkedNode*)malloc(sizeof(LinkedNode));
    node->data = data;
    node->next = NULL;
    if (queue->head == NULL) {
        queue->head = queue->tail = node;
        return;
    }
    queue->tail->next = node;
    queue->tail = node;
}

QueueElementType deQueue(Queue* queue) {
    // 取数据
    QueueElementType data = queue->head->data;
    // 移动头指针
    LinkedNode* node = queue->head;
    queue->head = node->next;
    // 释放内存
    free(node);
    
    return data;
}

/* 队列 end ********************/

/* 图 *************************/
// 因 INFINITY 已在math.h中定义，定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    for (int v=0; v < g->vertexNum; v++) {
        free(g->g[v]);
    }
    free(g->g);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
}

void readEdgeV1WithWeight(MGraph* g, int edgeNum) {
    g->edgeNum = edgeNum;
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, --v1, --v2, dist);
    }
}

void print1D(char* name, int array[], int n) {
    printf("%s: ", name);
    for (int i=0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}

/* 图 end *********************/

/* 图拓扑排序 ******************/
// 建立，并初始化顶点入度数组
int* initIndegree(MGraph* graph) {
    // 使用 calloc 方法，会把内容初始化为 0
    int* indegree = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 遍历图，得到indegree[] */
    for (int j=0; j < graph->vertexNum; j++) {
        // 第 j 个节点的入度，即与第 j 列连接的边数和
        for (int i=0; i < graph->vertexNum; i++) {
            if (isConnection(graph, i, j)) {
                indegree[j]++;
            }
        }
    }
    return indegree;
}

// 建立，并初始化顶点出度数组
int* initOutdegree(MGraph* graph) {
    int* outdegree = (int*) calloc(graph->vertexNum, sizeof(int));
    /* 遍历图，得到indegree[] */
    for (int i=0; i < graph->vertexNum; i++) {
        // 第 i 个节点的出度，即与第 i 行连接的边数和
        for (int j=0; j < graph->vertexNum; j++) {
            if (isConnection(graph, i, j)) {
                outdegree[i]++;
            }
        }
    }
    return outdegree;
}


WeightType max(WeightType w1, WeightType w2) {
    return w1 >= w2 ? w1 : w2;
}

WeightType min(WeightType w1, WeightType w2) {
    return w1 <= w2 ? w1 : w2;
}

int topSort(MGraph* graph, int topOrder[], int earliest[]) {
    /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
    int* indegree = initIndegree(graph);

    Queue* queue = createQueue();
    /* 将所有入度为0的顶点入列 */
    for (int i=0; i < graph->vertexNum; i++) {
        if (indegree[i] == 0) {
            enQueue(queue, i);
        }
        // 初始化 earliest
        earliest[i] = 0;
    }

    /* 下面进入拓扑排序 */ 
    int cnt = 0; 
    
    while (!isEmptyQueue(queue)) {
        /* 弹出一个入度为0的顶点 */
        int v = deQueue(queue); 
        topOrder[cnt++] = v; /* 将之存为结果序列的下一个元素 */
        
        /* 对V的每个邻接点W */
        for (int w=0; w < graph->vertexNum; w++) {
            // 计算 v 的 earliest
            // 这里 w 是 v 的前序节点
            if (isConnection(graph, w, v)) {
                // 有边<w, v>
                earliest[v] = max(earliest[v], earliest[w] + graph->g[w][v]);
            }
            // 这里  w 是 v 的后序节点
            if (isConnection(graph, v, w)) {
                // 有边<v, w>
                --indegree[w];
                /* 若删除V使得W入度为0 */
                if (indegree[w] == 0) {
                    /* 则该顶点入列 */
                    enQueue(queue, w);
                }
            }
        }
    }
    free(indegree);
    return cnt == graph->vertexNum;
}

// 获取数组中的最大值
int findMax(int a[], int n) {
    int max = 0;
    for (int i=0; i<n; i++) {
        if (a[i] > max) {
            max = a[i];
        }
    }
    return max;
}


void calLatest(MGraph *graph, int latest[], int maxTime) {
    int* outdegree = initOutdegree(graph);

    Queue* queue = createQueue();
    /* 将所有出度为0的顶点入列 */
    for (int i=0; i < graph->vertexNum; i++) {
        if (outdegree[i] == 0) {
            enQueue(queue, i);
        }
        // 初始化 latest
        latest[i] = maxTime;
    }

    while (!isEmptyQueue(queue)) {
        /* 弹出一个出度为0的顶点 */
        int j = deQueue(queue); 

        /* 对 j 的每个前序邻接点 i */
        for (int i=0; i < graph->vertexNum; i++) {
            if (isConnection(graph, i, j)) {
                // 有边<i, j>
                latest[i] = min(latest[i], latest[j] - graph->g[i][j]);
                --outdegree[i];
                /* 若删除 j 使得 i 出度为0 */
                if (outdegree[i] == 0) {
                    /* 则该顶点入列 */
                    enQueue(queue, i);
                }
            }
        }
    }
    free(outdegree);
}

// 计算关键路径，关键路径写入数组 path, 返回关键路径数量
int calImportantPath(MGraph *graph, int earliest[], int latest[], Edge path[]) {
    int cnt = 0;
    for (int i=0; i < graph->vertexNum; i++) {
        for (int j=0; j < graph->vertexNum; j++) {
            if (i!=j && latest[j] - earliest[i] - graph->g[i][j] == 0) {
                path[cnt++] = createEdge(i, j, graph->g[i][j]);
            }
        }
    }
    return cnt;
}

/* 图拓扑排序 end **************/

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 建立初始为最大权重的有向图
    MGraph* g = createGraph(DirectedGraph, MaxWeight, n);
    // 读取 m 条边
    readEdgeV1WithWeight(g, m);
    // printGraph(g);

    int* topOrder = (int*)calloc(n, sizeof(int));
    int* earliest = (int*)calloc(n, sizeof(int));
    int* latest = (int*)calloc(n, sizeof(int));
    Edge* path = (Edge*)calloc(m, sizeof(Edge));
    if (topSort(g, topOrder, earliest)) {
        int maxTime = findMax(earliest, n);
        printf("%d\n", maxTime);
        calLatest(g, latest, maxTime);
        // print1D("earliest", earliest, g->vertexNum);
        // print1D("latest", latest, g->vertexNum);
        int pathNum = calImportantPath(g, earliest, latest, path);
        for (int i=0; i<pathNum; i++) {
            printf("%d->%d\n", path[i].v+1, path[i].w+1);
        }
    } else {
        printf("0\n");
    }

    free(topOrder);
    free(earliest);
    free(path);
    freeGraph(g);
    return 0;
}
